/*************************************************************************
 * File Name:    Longest_Valid_Parentheses.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/16 13:38:54
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Longest Valid Parentheses
 | Given a string containing just the characters '(' and ')',
 | find the length of the longest valid (well-formed) parentheses substring.
 |
 | For "(()", the longest valid parentheses substring is "()", which has length = 2.
 |
 | Another example is ")()())", where the longest valid parentheses substring is "()()",
 | which has length = 4.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int longestValidParentheses(string s)
    {
        int N = s.size();
        stack<int> sta;
        vector<int> pre(N, -1);
        
        int ans, i, j;
        
        ans = 0;
        for (i = 0; i < N; ++i) {
            if (s[i] == '(') {
                sta.push(i);
            } else if (s[i] == ')') {
                if (!sta.empty()) {
                    pre[i] = sta.top();
                    sta.pop();
                }
            }
        }
        for (i = N - 1; i >= 0; --i) {
            if (pre[i] == -1) continue;
            for (j = i; j >= 0 && pre[j] != -1; j = pre[j] - 1);
            
            if (j < 0) ans = max(ans, i + 1);
            else ans = max(ans, i - j);
            i = j + 1;
        }
        
        return ans;
    }
};

